package C50;

/**
 * ClassName: C03
 * Package: C50
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/2/27 18:16
 * @Version 1.0
 * @Since 1.0
 */
public class C03 {
    public static void main(String[] args) {
        int[] arr = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(trap(arr));
        System.out.println(trap2(arr));
    }


    public static int trap(int[] height) {
        // 左amx数组
        int[] lmax = new int[height.length];
        // 右max数组
        int[] rmax = new int[height.length];

        lmax[0] = height[0];
        for (int i = 1; i < height.length; i++) {
            lmax[i] = Math.max(height[i], lmax[i - 1]);
        }

        rmax[height.length - 1] = height[height.length - 1];
        for (int i = height.length - 2; i >= 0; i--) {
            rmax[i] = Math.max(rmax[i + 1], height[i]);
        }

        int ans = 0;
        for (int i = 1; i < height.length - 1; i++) {
            ans += Math.max(Math.min(lmax[i - 1], rmax[i + 1]) - height[i],0);
        }
        return ans;
    }

    // 双指针的技巧
    public static int trap2(int[] height) {
        int lmax = height[0], rmax = height[height.length - 1], ans = 0;
        int lindex = 0, rindex = height.length - 1;
        while(lindex < rindex) {
            if(lmax > rmax) {
                ans += Math.max(0, rmax - height[--rindex]);
                rmax = Math.max(height[rindex], rmax);
            }else {
                ans += Math.max(0, lmax - height[++lindex]);
                lmax = Math.max(height[lindex], lmax);
            }
        }
        return ans;
    }
}
